package hot_100;

import java.util.*;

public class 前K个高频元素 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 2, 1, 2, 3, 1, 3, 2};
        int[] ints = topKFrequent(nums, 2);
        System.out.println(ints);
    }

    public static int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
            return a[1] - b[1];
        });
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        map.forEach((key, value) -> {
            if (queue.size() < k) {
                queue.add(new int[]{key, value});
            } else {
                int[] peek = queue.peek();
                if (value > peek[1]) {
                    queue.poll();
                    queue.add(new int[]{key, value});
                }
            }
        });
        ArrayList<Integer> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            ans.add(poll[0]);
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}
